//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

#include "List.h"

class Solution {
public:
    int getLength(ListNode* head)
    {
        int cnt = 0;
        while (head)
        {
            head = head->next;
            cnt++;
        }
        return cnt;
    }

    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) return head;
        int n = getLength(head);
        k %= n;
        if (k == 0) return head;

        //先找到倒数第k+1个结点
        auto p = head, q = head;
        for (int i = 0; i <= k; i++) p = p->next;
        while (p)
        {
            p = p->next;
            q = q->next;
        }
        p = q->next;
        q->next = NULL;

        //让 p 的后半部分链表最后一个结点接到整个链表（原链表）的前面
        q = p;
        while (q->next!=NULL) q = q->next;
        q->next = head;
        return p;
    }
};